#!/usr/bin/python
# Filename: LinkedList.py


class Node:
    '''Node'''
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = next
    def __str__(self):
        return str(self.value)

class LinkedList:
    '''Linked List'''    
    def __init__(self):
        self.length = 0
        # head and tail are not references but nodes,
        # this provides facility when insert and remove,
        # we have prev_node of the first node,
        # so the first node can be dealed with as other.
        # but tail node is not that useful.
        self.head = Node()
        self.tail = Node()
        
    def __str__(self):
        string = "["
        curr_node = self.head.next
        while curr_node:
            string += (str(curr_node) + ', ')
            curr_node = curr_node.next
        string +=  ']'
        return (string)

    def __len__(self):
        return self.length

    def __getitem__(self, key):
        if key < 0 or key > self.length-1:
            return None
        else:
            curr_node = self.head.next
            while key > 0:
                curr_node = curr_node.next
                key -= 1
            return curr_node.value

    def node(self, pos):
        if pos == -1: return self.head
        elif pos < -1 or pos > self.length-1: return None
        else:
            curr_node = self.head.next
            while pos > 0:
                curr_node = curr_node.next
                pos -= 1
            return curr_node

    def insert(self, value, pos=0):
        if pos < 0 or pos > self.length:
            # this will support insert to the end (append)
            return False
        node = Node(value)
        prev_node = self.node(pos-1)

        node.next = prev_node.next
        if prev_node.next == None:
            self.tail.next = node
        prev_node.next = node

        self.length += 1
        return True
    
    def append(self, value):
        node = Node(value)
        if self.length:
            self.tail.next.next = node
        else:
            self.head.next = node
        self.tail.next = node
        self.length += 1
        return True

    def remove(self, pos):
        if pos < 0 or pos > self.length-1:
            return None
        prev_node = self.node(pos-1)
        curr_node = self.node(pos)
        prev_node.next = curr_node.next
        self.length -= 1

        if prev_node.next == None:
        # end node is removed, this is ignored in the book
        # prev_node can be head.next
            self.tail.next = prev_node

        value = curr_node.value
        del curr_node
        return value
        
    def rev_string(self):
        self.rev_str = ']'
        curr_node = self.head.next
        while curr_node:
            self.rev_str = str(curr_node) + ", " + self.rev_str
            curr_node = curr_node.next
        self.rev_str = '[' + self.rev_str
        return (self.rev_str)

    def find(self, value):
        #ex_DSIntro_2_1
        curr_node = self.head.next
        l = []
        while curr_node:
            if curr_node.value == value:
                l.append(curr_node)
            curr_node = curr_node.next
        return l
        
    def reverse(self):
        # ex_DSIntro_work_2_1
        if not self.head.next: return False # empty list
        if not self.head.next.next: return True # one node list
        curr_node = self.head.next.next
        self.tail.next = self.head.next
        self.head.next.next = None
        while curr_node:
            node = curr_node
            curr_node = curr_node.next
            node.next = self.head.next
            self.head.next = node
        return True
         

class DNode:
    '''Dua Pointer Node'''
    def __init__(self, value=None, prev=None, next=None):
        self.value = value
        self.prev = prev
        self.next = next

    def __str__(self):
        return str(self.value)


class DLinkedList:
    '''Dua Direction Linked List'''
    def __init__(self):
        self.head = DNode()
        self.tail = DNode()
        self.length = 0

    def __str__(self):
        string = '['
        curr_node = self.head.next
        while curr_node != self.tail.next.next:
            string += (str(curr_node) + ", ")
            curr_node = curr_node.next
        string += ']'
        return string
        
    def __len__(self):
        return self.length

    def __getitem__(self, key):
        if key < 0 or key >= self.length:
            return None
        else:
            curr_node = self.head.next
            while key > 0:
                curr_node = curr_node.next
                key -= 1
            return curr_node.value
            
    def node(self, pos):
        if pos == -1: return self.head
        elif pos < -1 or pos > self.length-1: return None
        curr_node = self.head.next
        while pos > 0:
            curr_node = curr_node.next
            pos -= 1
        return curr_node
    
    def append(self, value):
        node = DNode(value)
        if self.length:
            self.tail.next.next = node
            node.prev = self.tail.next
            self.tail.next = node
        else:
            self.head.next = node
            self.tail.next = node
        self.length += 1

    def insert(self, value, pos=0):
        if pos < 0 or pos > self.length: return False
        prev_node = self.node(pos-1)
        node = DNode(value)

        node.next = prev_node.next
        if prev_node.next == None:
            # insert into the end
            self.tail.next = node
        else:
            # not the end
            node.next.prev = node
        prev_node.next = node

        if prev_node.prev != None:
            # not the first
            node.prev = prev_node

        self.length += 1
        return True

    def remove(self, pos):
        if pos < 0 or pos > self.length-1: return None
        prev_node = self.node(pos-1)

        node = prev_node.next
        value = node.value

        prev_node.next = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail.next = node.prev
        if node.prev:
        # else is done when prev_node.next(self.head.next) = node.next
            node.prev.next = node.next

        self.length -= 1
        del node
        return value


class OLinkedList:
    '''Circled Linked List'''
    pass


class ODLinkedList:
    '''Circled Dua Direction Linked List'''
    pass


if __name__ == "__main__":
    def test_linkedlist():
        print "LinkedList is under testing..."
        a = Node(1)
        print "new Node(a):",a
        b = Node(2)
        print "new Node(b):",b
        c = Node(3)
        print "new Node(c):",c
        l = LinkedList()
        print "new LinkedList(l):", l
        l.append(str(b))
        l.append(str(c))
        l.insert(str(a))
        l.insert('5', 3)
        l.insert('4', 3)
        l.append(6)
        print r"str(l):", l
        print "reversed l:", l.rev_string()

        print "l[1]:", l[1]
        print "l.remove(0):", l.remove(0), l
        print "l.remove(10):", l.remove(10)
        print "l.remove(len(l)-1):", l.remove(len(l)-1), l
        print "l.append('4'):", l.append('4'), l
        print "l.find('4'):", l.find('4')
        print "l.find(4):", l.find(4)
        print "l.find('5'):", l.find('5')
        print "l.reverse():", l.reverse(), l

    def test_dlinkedlist():
        print "DLinkedList is under testing..."
        dl = DLinkedList()
        dl.append(1)
        dl.append(2)
        dl.append(3)
        print "%s: %d" % (str(dl), len(dl))
        print "dl[1]:", dl[1]
        print "dl.node(1):", dl.node(1)
        print "dl.insert(0):", dl.insert(0)
        print dl
        print "dl.insert(5, 4):", dl.insert(5, 4)
        print dl
        print "dl.insert(4, 4):", dl.insert(4, 4)
        print dl
        print "dl.remove(10):", dl.remove(10)
        print "dl.remove(0):", dl.remove(0)
        print dl
        print "dl.remove(1):", dl.remove(1)
        print dl
        print "dl.remove(len(dl)-1):", dl.remove(len(dl)-1)
        print dl

    test_linkedlist()
#    test_dlinkedlist()

